package algorithm.recursionAndbacktrack.permuation.p47;

import java.util.ArrayList;
import java.util.List;

class Solution_v2 {
    public List<List<Integer>> permuteUnique(int[] nums) {
        ArrayList<List<Integer>> ans = new ArrayList<>();
        dfs(0, nums, ans);
        return ans;
    }

    void dfs(int level, int[] nums, List<List<Integer>> ans){
        if (nums.length == level){
            ArrayList<Integer> integers = new ArrayList<>();
            for (int num : nums) {
                integers.add(num);
            }
            ans.add(integers);
            return;
        }

        out:for (int i = level; i < nums.length; i++) {
            for(int j = level; j < i; j++){
                if(nums[j] == nums[i]) continue out;
            }
            swap(nums, level, i);
            dfs(level + 1, nums, ans);
            swap(nums, level, i);
        }
    }

    void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        System.out.println(new Solution_v2().permuteUnique(new int[]{1, 1, 2}));
    }
}